#include "junix.h"
#include <boost/bind.hpp>

using namespace std;

int partition2(int v[], int b,int e) {
	int p = v[e],l=b-1, r=e;
	while (true) {
		while (v[++l]<p) { }
		while (v[--r]>=p) 
			if (r==b) break;

		if (l>=r) break;
		swap(v[l],v[r]);
	}

	swap(v[l],v[e]);
	return l;
}

int partition(int v[], int b,int e) {
	int p=v[e], l=b-1, r=b;
	for (r=b;r<e;r++) {
		if (v[r]<p) 
			std::swap(v[++l],v[r]);
	}

	std::swap(v[++l], v[e]);
	return l;
}

void quiksort(int v[], int b, int e) {
	if (b>=e) return ;
	int i = partition2(v, b, e);
	quiksort(v, b, i-1);
	quiksort(v, i+1, e);
}

int main(int argc, char **argv)
{
	const int size = 10;
	vector<int> V(size);
	srand(time(0));

	generate(V.begin(),V.end(),
			boost::bind(modulus<int>(), boost::bind(rand), size));

	jtime timer;
	timer.start();
	quiksort(&V[0],0,V.size()-1);
	timer.end();
	timer.print();

	copy(V.begin(),V.end(),ostream_iterator<int>(cout," "));
	cout<<endl;
}
